import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)));
        System.out.println(Arrays.toString(s.searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6)));
        System.out.println(Arrays.toString(s.searchRange(new int[]{5}, 4)));
    }
}

//二刷
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = biSearchL(nums, target);
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        int right = biSearchR(nums, target);
        return new int[]{left, right};
    }

    int biSearchL(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    int biSearchR(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r;
    }
}




////二分查找小于target的最大值和大于target的最小值
//class Solution {
//    public int[] searchRange(int[] nums, int target) {
//        int l = biSearchMaxLT(nums, target) + 1;
//        int h = biSearchMinGT(nums, target, l) - 1;
//        if(l > h){
//            return new int[]{-1, -1};
//        }
//        return new int[]{l, h};
//    }
//
//
//    int biSearchMaxLT(int[] nums, int target){
//       int l = 0, h = nums.length - 1;
//       while(l <= h){
//           int mid = (l + h) / 2;
//           if(nums[mid] >= target){
//               h = mid - 1;
//           }
//           else{
//               l = mid + 1;
//           }
//       }
//       return h;
//    }
//
//    int biSearchMinGT(int[] nums, int target, int start){
//        int l = start, h = nums.length - 1;
//        while(l <= h){
//            int mid = (l + h) / 2;
//            if(nums[mid] <= target){
//                l = mid + 1;
//            }
//            else{
//                h = mid - 1;
//            }
//        }
//        return l;
//    }
//}